﻿#include <iostream>

#define MAX(a,b) (a>b?a:b)

static int longestLengthOfCommonSubSequence(const char* str1, const char* str2)
{
	if (!str1 || !str2) return 0;

	auto len1 = strlen(str1);
	auto len2 = strlen(str2);
	if (!len1 || !len2) return 0;

	size_t dpSize = len2 * sizeof(int);
	// 动态规划的压缩技巧，不需要建完整的2维数组了
	int* dp = (int*)malloc(dpSize);
	memset(dp, 0, dpSize);
	int* bakUpDp = (int*)malloc(dpSize);
	memset(bakUpDp, 0, dpSize);

	int up;
	int left;
	int upLeft;
	int tmp;
	int maxLen = 0;
	for (int i = 0; i < len1; i++)
	{
		for (int j = 0; j < len2; j++)
		{
			if (i == 0)
			{
				up = 0;
			}
			else
			{
				up = bakUpDp[j];
			}

			if (j == 0)
			{
				left = 0;
			}
			else
			{
				left = dp[j - 1];
			}
		
			upLeft = (i > 0 && j > 0) ? bakUpDp[j - 1] : 0;

			if (str1[i] == str2[j])
			{
				++upLeft;
			}

			tmp = MAX(left, upLeft);
			dp[j] = MAX(up, tmp);
			maxLen = MAX(maxLen, dp[j]);
		}

		memcpy_s(bakUpDp, dpSize, dp, dpSize);
	}

	free(dp);
	free(bakUpDp);
	return maxLen;
}

/**
 * 请注意区分子序列和子串的不同，给定的两个字符串str1和str2，求两个字符串的最长公共子序列。
 * 
 * 思路：
 * 以str1[i]和str2[j]结尾，最长公共子序列是什么？
 * 情况1: 当且仅当str1[i]==str2[j]时，子序列以str1[i]结尾，以str2[j]结尾
 *    看(i-1,j-1)，则(i-1,j-1)+1
 * 情况2: 子序列以str1[i]结尾，但是不以str2[j]结尾
 *    有j没j是一样的，所以看(i,j-1)
 * 情况3: 子序列不以str1[i]结尾，但是以str2[j]结尾
 *    有i没i是一样的，所以看(i-1,j)
 * 情况4: 子序列既不以str1[i]结尾，也不以str2[j]结尾
 *    看(i-1,j-1)
 * 
 * 这四种情况取最大值
 * 
 * 设str1="aebcdpefoh", str2="uaeklbcyejfvb"
 * 
 *          u  a  e  k  l  b  c  y  e  j  f  v  b
 *          0  1  2  3  4  5  6  7  8  9 10 11 12 j
 * -------------------------------------------------
 *    a  0| 0  1  1  1  1  1  1  1  1  1  1  1  1
 *    e  1| 0  1  2  2  2  2  2  2  2  2  2  2  2
 *    b  2| 0  1  2  2  2  3  3  3  3  3  3  3  3
 *    c  3| 0  1  2  2  2  3  4  4  4  4  4  4  4
 *    d  4| 0  1  2  2  2  3  4  4  4  4  4  4  4
 *    p  5| 0  1  2  2  2  3  4  4  4  4  4  4  4
 *    e  6| 0  1  2  2  2  3  4  4  5  5  5  5  5
 *    f  7| 0  1  2  2  2  3  4  4  5  5  6  6  6
 *    o  8| 0  1  2  2  2  3  4  4  5  6  6  6  6
 *    h  9| 0  1  2  2  2  3  4  4  5  6  6  6  6
 *       i|
 * 
 * 还是将i==0和j==0时的先填好，然后根据四种情况，由(i-1,j),(i,j-1),(i-1,j-1)3个位置的元素求出(i,j)
 */
int main_longestCommonSubSequence()
{
	auto maxLen = longestLengthOfCommonSubSequence("a32bc1de34fg", "ab767cd9e9f0g");
	printf("%d", maxLen);
	return 0;
}